#include <iostream>
#include <vector>
#include <cassert>

// Definition for singly-linked list.
struct ListNode {
    int val;
    ListNode *next;
    ListNode() : val(0), next(nullptr) {}
    ListNode(int x) : val(x), next(nullptr) {}
    ListNode(int x, ListNode *next) : val(x), next(next) {}
};

class Solution {
public:
    ListNode* reverseList(ListNode* head) {
        ListNode *cur = head, *pre = nullptr;
        while (cur != nullptr) {
            ListNode* tmp = cur->next;
            cur->next = pre;
            pre = cur;
            cur = tmp;
        }
        return pre;
    }
};

// 工具函数：创建链表（从数组）
ListNode* createList(const std::vector<int>& vals) {
    if (vals.empty()) return nullptr;
    ListNode* head = new ListNode(vals[0]);
    ListNode* cur = head;
    for (size_t i = 1; i < vals.size(); ++i) {
        cur->next = new ListNode(vals[i]);
        cur = cur->next;
    }
    return head;
}

// 工具函数：打印链表
void printList(ListNode* head) {
    ListNode* cur = head;
    while (cur) {
        std::cout << cur->val;
        if (cur->next) std::cout << " -> ";
        cur = cur->next;
    }
    std::cout << " (null)" << std::endl;
}

// 工具函数：释放链表内存
void deleteList(ListNode* head) {
    while (head) {
        ListNode* temp = head;
        head = head->next;
        delete temp;
    }
}

// 工具函数：将链表转为 vector 用于比较
std::vector<int> listToVector(ListNode* head) {
    std::vector<int> result;
    ListNode* cur = head;
    while (cur) {
        result.push_back(cur->val);
        cur = cur->next;
    }
    return result;
}

int main() {
    Solution solution;

    // 测试用例 1: 正常链表 [1,2,3,4,5]
    {
        std::vector<int> input = {1, 2, 3, 4, 5};
        ListNode* head = createList(input);
        std::cout << "Test 1 - Original: ";
        printList(head);

        ListNode* reversed = solution.reverseList(head);
        std::cout << "         Reversed: ";
        printList(reversed);

        std::vector<int> expected = {5, 4, 3, 2, 1};
        std::vector<int> actual = listToVector(reversed);
        assert(actual == expected && "Test 1 failed");
        std::cout << "✅ Test 1 passed!" << std::endl;
        deleteList(reversed);
        std::cout << std::endl;
    }

    // 测试用例 2: 单个节点 [1]
    {
        std::vector<int> input = {1};
        ListNode* head = createList(input);
        std::cout << "Test 2 - Original: ";
        printList(head);

        ListNode* reversed = solution.reverseList(head);
        std::cout << "         Reversed: ";
        printList(reversed);

        std::vector<int> expected = {1};
        std::vector<int> actual = listToVector(reversed);
        assert(actual == expected && "Test 2 failed");
        std::cout << "✅ Test 2 passed!" << std::endl;
        deleteList(reversed);
        std::cout << std::endl;
    }

    // 测试用例 3: 空链表 []
    {
        ListNode* head = nullptr;
        std::cout << "Test 3 - Original: (null)" << std::endl;

        ListNode* reversed = solution.reverseList(head);
        std::cout << "         Reversed: ";
        if (reversed == nullptr) {
            std::cout << "(null)" << std::endl;
        } else {
            printList(reversed);
        }

        assert(reversed == nullptr && "Test 3 failed");
        std::cout << "✅ Test 3 passed!" << std::endl;
        std::cout << std::endl;
    }

    // 测试用例 4: 两个节点 [1,2]
    {
        std::vector<int> input = {1, 2};
        ListNode* head = createList(input);
        std::cout << "Test 4 - Original: ";
        printList(head);

        ListNode* reversed = solution.reverseList(head);
        std::cout << "         Reversed: ";
        printList(reversed);

        std::vector<int> expected = {2, 1};
        std::vector<int> actual = listToVector(reversed);
        assert(actual == expected && "Test 4 failed");
        std::cout << "✅ Test 4 passed!" << std::endl;
        deleteList(reversed);
        std::cout << std::endl;
    }

    // 测试用例 5: 重复值 [3,3,3]
    {
        std::vector<int> input = {3, 3, 3};
        ListNode* head = createList(input);
        std::cout << "Test 5 - Original: ";
        printList(head);

        ListNode* reversed = solution.reverseList(head);
        std::cout << "         Reversed: ";
        printList(reversed);

        std::vector<int> expected = {3, 3, 3}; // 反转后仍相同
        std::vector<int> actual = listToVector(reversed);
        assert(actual == expected && "Test 5 failed");
        std::cout << "✅ Test 5 passed!" << std::endl;
        deleteList(reversed);
        std::cout << std::endl;
    }

    std::cout << "All tests passed! ✅✅✅" << std::endl;

    return 0;
}